//
// Created by fengg on 2020/5/24.
//


#include <stdio.h>
#include <stdlib.h>


void DisplayIArray(int *lpArray,int iLower,int iUpper) {
    int i;
    for (i = iLower; i <= iUpper; ++i) {
        printf("%d ",lpArray[i]);
    }
    putchar('\n');
}

void Swap(int *lpArray, int j, int i) {
    int iTemp;
    if (j < 0 || i < 0) {
        return;
    }
    iTemp = lpArray[j];
    lpArray[j] = lpArray[i];
    lpArray[i] = iTemp;
}

void ShakerSort(int *lpArray, int iLower, int iUpper) {
    int iCurrUpper = iUpper;
    int iCurrLower = iLower;
    int j;
    int changed = 0;
    for (; iCurrLower <= iCurrUpper; --iCurrUpper,++iCurrLower) {
        for (j = iCurrLower; j <= iCurrUpper-1; ++j)
            if(lpArray[j] > lpArray[j+1])
                Swap(lpArray,j,j+1),changed = 1;
        for (j = iCurrUpper; j >= iCurrLower+1; --j)
            if(lpArray[j] < lpArray[j-1])
                Swap(lpArray,j,j-1),changed = 1;
        if(changed)
            DisplayIArray(lpArray,iLower,iUpper),changed = 0;
    }
}

int main(){
    int *lpArray;
    int iNumber;
    int i;
    scanf("%d",&iNumber);
    lpArray = malloc(sizeof(int)*iNumber);
    for (i = 0; i < iNumber; ++i) {
        scanf("%d",&lpArray[i]);
    }

    DisplayIArray(lpArray,0,iNumber-1);
    ShakerSort(lpArray,0,iNumber-1);
    DisplayIArray(lpArray,0,iNumber-1);

    return 0;
}